#include <iostream>
#include <vector>
#include <algorithm>
#include <sys/time.h>

using namespace std;


void movezero(vector<int>& nums,int begin,int end)
{
   if(begin==end)
     return;

   if( nums.at(begin)==0 )
   {
     //shift begin number to the end;

     int tmp = nums.at(begin);
     for(int i=begin; i<end; ++i)
     {
       nums[i] = nums[i+1];
     }
     nums[end]=tmp;

     movezero(nums,begin,end-1);
   }
   else
   {
     movezero(nums,begin+1,end);
   }

}


void moveZeroes(vector<int>& nums) 
{
  int end = nums.size()-1;
  if(end<=0)
  {
    return;
  }
  movezero(nums,0,end);

}

int main(int argc,char *argv[])
{

  struct  timeval    tv1,tv2;
  struct  timezone   tz;
  int time1 = gettimeofday(&tv1,&tz);

  vector<int> nums={0,1,0,3,12};
   
  moveZeroes(nums);

  for(auto i:nums)
    cout<<i<<",";
  cout<<endl;

  int time2 = gettimeofday(&tv2,&tz);
  cout << "time consuming(local machine/leetcode server):"<<endl
    <<"leetcode server time consuming should be less than 500ms"<<endl
    << tv2.tv_usec - tv1.tv_usec <<"us/"<<0.11*( tv2.tv_usec - tv1.tv_usec )<<"ms"<< endl;



  return 0;
}
